package class05;

import java.util.HashMap;
import java.util.Map;

//https://leetcode.cn/problems/longest-consecutive-sequence/?envType=problem-list-v2&envId=union-find&
public class Code_05LongestConsecutive {
    public static int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int m = nums.length;
        UnionFind uf = new UnionFind(m);
        for (int i = 0; i < m; i++) {
            if (map.containsKey(nums[i])) continue;

            if (map.containsKey(nums[i] - 1)) {
                uf.union(i, map.get(nums[i] - 1));
            }
            if (map.containsKey(nums[i] + 1)) {
                uf.union(i, map.get(nums[i] + 1));
            }
            map.put(nums[i], i);
        }
        return uf.getMaxSize();

    }

    public static class UnionFind {
        private int[] parent;
        private int[] size;
        private int[] help;
        private int sets;

        public UnionFind(int n) {
            parent = new int[n];
            help = new int[n];
            size = new int[n];
            sets = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }

        }

        int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        public void union(int x, int y) {
            int f1 = find(x);
            int f2 = find(y);
            if (f2 != f1) {
                if (size[f1] >= size[f2]) {
                    parent[f2] = f1;
                    size[f1] += size[f2];
                } else {
                    parent[f1] = f2;
                    size[f2] += size[f1];
                }
                sets--;
            }
        }

        int getMaxSize() {
            int ans = 0;
            for (int i = 0; i < size.length; i++) {
                ans = Math.max(ans, size[i]);
            }
            return ans;
        }

    }


    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{0, -1}));


    }
}




